package com.jeasonzhao.commons.inplacecache;

import java.util.HashMap;
import java.util.Iterator;

/**
 * LFU (least frequently used) cache.
 *
 * <p>
 * Frequency of use data is kept on all items. The most frequently used items are kept in the cache.
 * Because of the bookkeeping requirements, cache access overhead increases logarithmically with cache size.
 * The advantage is that long term usage patterns are captured well, incidentally making the algorithm scan resistant;
 * the disadvantage, besides the larger access overhead, is that the algorithm doesn't adapt quickly to changing
 * usage patterns, and in particular doesn't help with temporally clustered accesses.<br>
 * Summary for LFU: not fast, captures frequency of use, scan resistant.
 */
public class LFUCache<K,V> extends AbstractCacheMap<K,V>
{

    public LFUCache(int maxSize)
    {
        this(maxSize,0);
    }

    public LFUCache(int maxSize,long timeout)
    {
        super(maxSize,timeout,new HashMap<K,CacheObject<K,V>>(maxSize + 1));
    }

    @Override
    public int prune()
    {
        int count = 0;
        CacheObject<K,V> comin = null;
        Iterator<CacheObject<K,V>> values = null == this.getCacheMap() ? null : this.getCacheMap().values().iterator();
        while(null != values && values.hasNext())
        {
            CacheObject<K,V> co = values.next();
            if(co.isExpired() == true)
            {
                values.remove();
                count++;
                continue;
            }

            if(comin == null)
            {
                comin = co;
            }
            else
            {
                if(co.getAccessCount() < comin.getAccessCount())
                {
                    comin = co;
                }
            }
        }

        if(isFull() == false)
        {
            return count;
        }
        if(comin != null)
        {
            values = null == this.getCacheMap() ? null : this.getCacheMap().values().iterator();
            while(values != null && values.hasNext())
            {
                CacheObject<K,V> co = values.next();
                co.setAccessCount(co.getAccessCount() - comin.getAccessCount());
                if(co.getAccessCount() <= 0)
                {
                    values.remove();
                    count++;
                }
            }
        }
        return count;
    }

}
